\documentclass[11pt]{llncs}
\usepackage{amsmath,amssymb,times,a4wide}
%\usepackage{showkeys}


\def\floor#1{\mathop{\left\lfloor#1\right\rfloor}}
\def\ceil#1{\mathop{\left\lceil#1\right\rceil}}
\def\Prob{\mathrm{I\mskip-3.6mu Pr}}
\def\Exp{\mathrm{I\mskip-3.6mu E}}

\def\st{\setminus}
\def\union{\cup}
\def\cut{\cap}
\def\eps{\varepsilon}

\def\NP{\mathcal{NP}}
\newcommand{\reals}{\mathrm{I\!R}}
\newcommand{\nats}{\mathrm{I\!N}}

\def\OPT{\mathrm{OPT}}
\def\SC{\mathrm{SC}}
\def\PFL{\mathrm{LPart}}
\def\Prop{\mathrm{WIProp}}
\def\OFL{\mathrm{OFL}}

\def\cost{\mathrm{cost}}
\def\Ball{\mathrm{Ball}}
\def\davg{\overline{d}}

\def\l{\lambda}

\def\l{\chi}
\def\r{\chi'}

\def\C{C^\ast}
\def\c{c^\ast}
\def\dst{d^\ast}
\def\D{D}

\def\med{\mathop{\mathrm{med}}}
\def\I{\mathcal{I}}
\def\Ithr{\mathcal{I}_3}
\def\IthrS{\mathcal{I}_3^-}
\def\IthrL{\mathcal{I}_3^+}
\def\sep{\!\!:\!\!}


\spnewtheorem*{proofsketch}{Proofsketch}{\itshape}{\rmfamily}
\spnewtheorem{myclaim}{Claim}{\bfseries}{\itshape}
\spnewtheorem{mechanism}{Mechanism}{\bfseries}{\itshape}

%\newenvironment{proofsketch}{\begin{trivlist}
%        \item[\hspace{\labelsep}{\noindent\emph{Proofsketch.}}]}
%        {\qed\end{trivlist}}
%\newenvironment{remark}{\begin{trivlist}%
%       \item[\hspace{\labelsep}{\noindent\emph{Remark.}}]}
%       {\end{trivlist}}

\newcommand{\frage}[2]{{\sl#1}{\marginpar{{%
        \fontsize{8pt}{8pt}\selectfont%
        \begin{flushleft}{\sl#2}\end{flushleft}}}}}



\def\insertfig#1#2#3{%
\begin{figure}[t]
\centerline{\includegraphics[width=#1]{#2}}
\caption{#3}
\end{figure}}

%\renewcommand{\baselinestretch}{1.1}

\pagenumbering{arabic}%

%\newpage
\pagestyle{plain}
\pagenumbering{arabic}

\begin{document}

\section{Overview of the Mechanisms}

(Since there are many mechanisms and take a lot of space, we can put this in the appendix. It is good to have all the known mechanisms together in the same place. We can reference the appropriate mechanism inside the text)

\subsection{Deterministic}
\begin{mechanism}[Two-Extremes]
\label{mech-extremes}
Place facilities in the leftmost and rightmost location, $F(\vec{x}) = ( \min \vec{x}, \max \vec{x} )$.
\end{mechanism}

%\cite{PT09}
\begin{theorem}[!!Cite!!]
\label{th-extremes}
Mechanism \ref{mech-extremes} is strategyproof and $(n-2)$-approximate.
\end{theorem}

\begin{mechanism}[Dictatorial]
\label{mech-dictatorial}
Choose an arbitrary dictator $j$ and place one facility at his location. Then consider the distance of the dictator from the leftmost and rightmost locations, $d_l = | \min \vec{x} - x_j|$ and $d_r = | \max \vec{x} - x_j|$. If $d_l > d_r$ the second facility is placed at position $x_j - \max \{ d_l, 2 d_r \}$, otherwise it is placed at $x_j + \max \{ d_r, 2 d_l \}$.
\end{mechanism}

\begin{theorem}[!!Cite!!]
\label{th-dictatorial}
Mechanism \ref{mech-dictatorial} is strategyproof and $(n-1)$-approximate.
\end{theorem}

When $n=3$ there exists a different mechanism that is strategyproof and has bounded approximation ratio which doesn't choose a global dictator but a partial one.

\begin{mechanism}[Combined - 3 agents]
\label{mech-combined}
Choose an arbitrary permutation of the agents $(i,j,k)$. Whenever $x_i < x_k$ allocate the facilities according to Mechanism \ref{mech-extremes}, otherwise allocate facilities according to Mechanism \ref{mech-dictatorial} with agent $j$ as dictator.
\end{mechanism}

\begin{theorem}[!!Cite!!]
\label{th-combined}
Mechanism \ref{mech-combined} is strategyproof and $2$-approximate.
\end{theorem}

\subsection{Randomized}

For the case of two facilities the best known randomized mechanism is the proportional mechanism.
\begin{mechanism}[Proportional]
\label{mech-proportional}
Choose an agent $j$ uniformly at random and place one facility at his location. Next consider the distance $d_i$ of every  agent $i$ to the selected agent $j$. Place the second facility at the location $x_i$ of agent $i$ with probability equal to $\frac{ d_i}{\sum_{k \in N} d_k}$.
\end{mechanism}


\begin{theorem}[!!Cite!!]
\label{th-proportional}
Mechanism \ref{mech-proportional} is strategyproof and $4$-approximate.
\end{theorem}

Mechanism \ref{mech-proportional} can be extended to 3 facilities on the line.

\begin{mechanism}[Proportional - 3 facilities]
\label{mech-proportional3}
Place facilities in the leftmost and rightmost location, $\{ \min \vec{x}, \max \vec{x} \} \subset F(\vec{x})$.
Next consider the distance $d_i$ of every agent $i$ to the closest of the two extremes. Place the third facility at the location $x_i$ of agent $i$ with probability equal to $\frac{ d_i}{\sum_{k \in N} d_k}$.
\end{mechanism}

\begin{theorem}[!!Cite!!]
\label{th-proportional3}
Mechanism \ref{mech-proportional3} is strategyproof and $(n-1)$-approximate.
\end{theorem}

For $k$ facilities with $k>3$, the only case where strategyproof mechanisms with bounded approximation ratio are known is when $n=k+1$. In these cases we choose an agent that will not be assigned a facility and place facilities in all other agents locations.

\begin{mechanism}[Inversely Proportional]
\label{mech-invproportional}
Let $d_i$ be the distance  of every agent $i$ to its closest neighbor. Place the facilities in the locations of all agents except $i$ with probability equal to $\frac{ d^{-1}_i}{\sum_{k \in N} d^{-1}_k}$.
\end{mechanism}

\begin{theorem}[!!Cite!!]
\label{th-invproportional}
Mechanism \ref{mech-invproportional} is strategyproof and $n/2$-approximate.
\end{theorem}

\subsection{Imposing}

In the imposing setting there exist different classes of deterministic mechanisms even in the case where $k=2$. For example, a slight modification of Mechanism \ref{mech-dictatorial} is also strategyproof with bounded approximation ratio.

\begin{mechanism}
\label{mech-imposing2}
Place one facility at the median location $m = \med \vec x$. Then consider the distance of the median from the leftmost and rightmost locations, $d_l = | \min \vec{x} - m|$ and $d_r = | \max \vec{x} - m|$. If $d_l > d_r$ the second facility is placed at position $m - \max \{ d_l, 2 d_r \}$, otherwise it is placed at $m + \max \{ d_r, 2 d_l \}$.
\end{mechanism}


\begin{theorem}[!!Cite!!]
\label{th-imposing2}
Mechanism \ref{mech-imposing2} is strategyproof and $(n-1)$-approximate.
\end{theorem}

This example, even though it doesn't break the lower bound of $n-2$, it shows that the class of imposing mechanisms is richer. In the
case where $k=3$ however, there imposing requirement allows us to design nice anonymous mechanisms which don't exist in the non-imposing setting.

\begin{mechanism}
\label{mech-imposing3}
Place facilities in the leftmost and rightmost location, $\{ \min \vec{x}, \max \vec{x} \} \subset F(\vec{x})$. Let $A$ and $B$ be the set of agents on
$[ \min \vec{x},  x_m ] $ and $(x_m, \max \vec{x}]$ respectively with $x_m = \frac{ \min \vec{x}+ \max \vec{x}} 2$. Define
$d_A = \max_{i \in A} | \min \vec{x} - x_i |$ and $d_B = \max_{i \in B} | \max \vec{x} - x_i |$. We
allocate the third facility as follows:
\begin{itemize}
\item If $d_A \ge d_B$, the third facility is placed at $\min\{x_m,  \min \vec{x} + \max\{d_A, 2 d_B\}\}$.
\item If $d_A < d_B$, the third facility is placed at $\max\{x_m, \max \vec x - \min\{2 d_A, d_B\}\}$.
\end{itemize}
\end{mechanism}

\begin{theorem}[!!Cite!!]
\label{th-imposing3}
Mechanism \ref{mech-imposing3} is strategyproof and $(n-1)$-approximate.
\end{theorem}

The imposing setting allows us to design efficient strategyproof mechanisms in the randomized case as well. The extension of Mechanism \ref{mech-proportional} to more than 3-facilities is strategyproof under the imposing setting.

\begin{mechanism}[Imposing Proportional]
\label{mech-impproportional}
Choose an agent $j$ uniformly at random and place one facility at his location. For each of the other facilities, consider the distance $d_i$ of every agent $i$ to his closest facility placed so far. Place a facility at the location $x_i$ of agent $i$ with probability equal to $\frac{ d_i}{\sum_{k \in N} d_k}$.
\end{mechanism}

\begin{theorem}[!!Cite!!]
\label{th-impproportional}
Mechanism \ref{mech-impproportional} is strategyproof and $4 k$-approximate.
\end{theorem}


\bibliographystyle{plain}
%\bibliography{mechdesign2}

\end{document}
